package 数组;
import java.util.*;
/**
 * 除自身以外数组的乘积
 * 给定一个数组，返回一个新数组，其中每个元素是原数组除该位置元素外的所有元素的乘积
 * 要求：时间复杂度O(n)，空间复杂度O(1)（不考虑输出数组的空间）
 */
public class productExceptSelf {
    /**
     * 使用两个数组的方法计算除自身以外数组的乘积
     * 时间复杂度：O(n)，空间复杂度：O(n)
     * 
     * @param nums 输入数组
     * @return 除自身以外数组的乘积
     */
    public int[] product2Array(int[] nums){
        int len = nums.length;
        int[] res = new int[len]; // 结果数组
        
        int[] le = new int[len]; // 存储每个位置左侧所有元素的乘积
        int[] ri = new int[len]; // 存储每个位置右侧所有元素的乘积
        
        le[0] = 1; // 第一个元素左侧没有元素，乘积为1
        for(int i = 1; i < len; i++){ // 计算每个位置左侧所有元素的乘积
            le[i] = le[i - 1] * nums[i - 1];
        }
        ri[len - 1] = 1; // 最后一个元素右侧没有元素，乘积为1
        for(int i = len - 2; i >= 0; i--){ // 计算每个位置右侧所有元素的乘积
            ri[i] = ri[i + 1] * nums[i + 1];
        }
        for(int i = 0; i < len; i++){ // 计算最终结果
            res[i] = le[i] * ri[i]; // 每个位置的结果等于左侧乘积乘以右侧乘积
        }
        return res;
    }

    /**
     * 使用一个数组的方法计算除自身以外数组的乘积
     * 时间复杂度：O(n)，空间复杂度：O(1)（不考虑输出数组的空间）
     * 
     * @param nums 输入数组
     * @return 除自身以外数组的乘积
     */
    public int[] productExcepSel(int[] nums){
        int len = nums.length;
        int[] res = new int[len]; // 结果数组

        res[0] = 1; // 第一个元素左侧没有元素，乘积为1
        for(int i = 1; i < len; i++){ // 计算每个位置左侧所有元素的乘积
            res[i] = res[i - 1] * nums[i - 1];
        }
        int ri = 1; // 用于存储右侧所有元素的乘积
        for(int j = len - 2; j >= 0; j--){ // 从右向左遍历
            ri = ri * nums[j + 1]; // 更新右侧乘积
            res[j] = ri * res[j]; // 计算最终结果
        }
        return res;
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示输入数组
     * 例如：1,2,3,4 表示一个输入数组
     * 输出格式：两种方法计算的结果
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int[] nums = new int[s.length]; // 创建输入数组
        for(int i = 0; i < s.length; i++){ // 将输入转换为整数数组
            nums[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        productExceptSelf pes = new productExceptSelf(); // 创建实例
        System.out.println("two array:" + Arrays.toString(pes.product2Array(nums))); // 输出两个数组方法的结果
        System.out.println("one array:" + Arrays.toString(pes.productExcepSel(nums))); // 输出一个数组方法的结果
        sc.close(); // 关闭输入流
    }
}
